In related art, a Serial Dictatorship mechanism (hereinafter referred to as “SD mechanism”) is known, as matching processing to assign a number of applicants (such as children of guardians who desire childcare) to application targets (such as nursery schools) (Svensson, Lars-Gunnar, “Strategy-proof allocation of indivisible goods,” Social Choice and Welfare 16.4 (1999): 557-567.). In the SD mechanism, ranks of priority are assigned to the applicants, and the applicants are allocated to the application targets that the applicants desire, among the application targets that are left at the point in time, in order from the applicant with the highest rank of priority. The SD mechanism guarantees that the ranks of priority are not reversed.
However, the related art described above has the problem that proper assignment to the application target is difficult in the case where the applicants include applicants who request coupling.
For example, in application to a plurality of day nurseries, there are cases where the guardian requests coupling of one's children being siblings (such as brothers, an elder brother and a younger sister, an elder sister and a younger brother, and sisters). Because the SD mechanism is not a mechanism made in consideration of applicants who request coupling of siblings, the SD mechanism may fail to obtain proper matching results (allocation), when the applicants include applicants who request coupling of siblings. For example, one of the following problems 1 to 3 may occur in matching.
Problem 1: Another applicant with a rank of priority lower than the applicant oneself enters the day nursery that the applicant oneself desires to enter (regardless of existence of siblings).
Problem 2: As siblings, applicants (they are not always siblings), both of whom have ranks of priority lower than that of the applicant oneself, enter the day nursery that the applicant oneself desires to enter.
Problem 3: The siblings enter separate day nurseries, although allocation to cause siblings to enter the same day nursery with a low desired order is better than allocation to cause siblings to enter separate day nurseries in accordance with their individual ranks of priority.
FIG. 19 to FIG. 21 are explanatory drawings illustrating the first to the third cases. In the examples of FIG. 19 to FIG. 21, the applicants 202a are matched with the application targets 201a, based on the same application target information 201 and applicant information 202.
The application target information 201 is information for the application targets 201a (day nurseries in the illustrated example), in which the numbers of acceptable children and the like in the application targets 201a are preset. In the illustrated example, the number of acceptable children is set to two in each of day nurseries “S1” to “S3”.
The applicant information 202 is information set for the applicants 202a (children in the illustrated example) in advance for applications of the respective guardians. Specifically, the applicant information 202 has a structure in which, in each of application IDs indicating applications, the points to determine the rank of priority and the order of desired nurseries indicating the ranking of the desired application targets 201a, for each of child IDs identifying the applicant children. For example, the ranks of priority are assigned to the applicants 202a in the order of their points, highest first, in the applicant information 202. When one application ID includes a plurality of child IDs, the child IDs indicate children who have a sibling relation, and the application ID includes a coupling request between the children.
As illustrated in FIG. 19, in the first case C1, the sibling relations (coupling requests) are ignored, and the applicants 202a are assigned to the application targets 201a by the SD mechanism, based on the application target information 201 and the applicant information 202. Specifically, the applicants 202a are assigned to their desired application targets 201a (S201 to S206), in order from the applicant 202a with the highest rank of priority (the order of I1, J1, K1, K2, L1, and I2 in the illustrated example).
As described above, the problem 3 occurs in the first case C1 in which assignment is performed by the SD mechanism, with the coupling requests ignored. Specifically, the siblings of K1 and K2 are not admitted to the same day nursery, even to a day nursery (such as S2) with a low desired rank, but admitted to separate day nurseries.
As illustrated in FIG. 20, in the second case C2, assignment is performed in the form in which the children with a sibling relation (coupling request) are put together (S211 to S214). In the second case C2, when the children with a sibling relation are put together, the points of the coupled children are set to the higher point of the two.
As illustrated in FIG. 21, also in the third case C3, assignment is performed in the form in which the children with a sibling relation (coupling request) are put together (S221 to S224). In the third case C3, when the children with a sibling relation are put together, the points of the coupled children are set to the lower point of the two.
As described above, in the second case C2 and the third case C3 in which assignment is performed in the form in which the applicants are put together in accordance with coupling requests, the problem 1 occurs because the individual ranks of priority are distorted. Specifically, in the second case C2, the applicant 202a of I2 having the rank of priority lower than that of L1 is assigned to the desired application target 201a (S1 in the illustrated example), and the ranks of priority are reversed. In addition, in the third case C3, the applicants 202a of K1 and K2 having the ranks of priority lower than that of I1 are assigned to the desired application target 201a (S1 in the illustrated example), and the ranks of priority are reversed.
As described above, when the applicants are assigned by the SD mechanism with the sibling relations (coupling requests) ignored, the problem 3 frequently occurs. In addition, when the applicants are assigned in the form in which siblings are put together (in accordance with coupling requests), the problem 1 frequently occurs.
When matching in the form in which children having sibling relations are put together is searched for to minimize these problems, obtaining stable matching becomes difficult in the case where preconditions in matching changes, such as the number of children to be admitted is determined for each of classes divided by age. In addition, such a case requires a large quantity of calculation.